/**
 * @Date 2024/5/28 10:39
 * @description: 力扣37: 解数独
 * .
 * @Author LittleNight
 */
public class likou37 {

    boolean[][] row; // 用于判断这个数在这一行有没有出现过
    boolean[][] col;
    boolean[][][] grid; // 用于判断这个数在小的九宫格内有没有出现过
    public void solveSudoku(char[][] board) {
        row = new boolean[9][10]; // 列给10个空间表示 0-9,不用映射2-1 3-2了
        col = new boolean[9][10];
        grid = new boolean[9][9][10];
        // 初始化
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                // 先判断是数字
                if(board[i][j] != '.') {
                    int num = board[i][j] - '0'; // 得到数字
                    row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true; // 表示出现过了
                }
            }
        }
        dfs(board); // 看题目一定是有解的
    }
    public boolean dfs(char[][] board) {
        // 主逻辑
        for (int i = 0;i < 9; i++) {
            for (int j = 0;j < 9; j++) {
                // 先判断是数字
                if(board[i][j] == '.') {
                    // 不是数字, 填数字
                    for(int k = 1; k <= 9; k++) {
                        int num = k;
                        // 没有出现过
                        if(row[i][num] == false && col[j][num] == false && grid[i / 3][j / 3][num] == false) {
                            board[i][j] = (char)(num + '0');
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true; // 表示出现过了
                            // dfs(board); // 递归下一个数
                            if(dfs(board)) return true; // 重点理解
                            // 回溯-恢复现场
                            board[i][j] = '.';
                            row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = false; // 表示没有出现过
                        }
                    }
                    // 走到这说明没有返回true, 说明 1-9 都填不了,直接返回false, 后面的也都是错的
                    return false; // 重点理解
                }
            }
        }
        // 说明这个数独已经填完了
        return true; //重点理解
    }
}
